#define _CRT_SECURE_NO_WARNINGS 1

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<vector>

using namespace std;

//const int N = 110;
//
//long long f[N], n;
//
//int main()
//{
//    f[0] = 1, f[1] = 1;
//    for (int i = 2; i < N; i++)
//    {
//        f[i] = f[i - 1] + f[i - 2];
//    }
//    scanf("%d", &n);
//    int l = 0, r = N - 1;
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (f[mid] >= n)
//        {
//            r = mid;
//        }
//        else
//        {
//            l = mid + 1;
//        }
//    }
//    int res1 = f[r] - n;
//    int res2 = n - f[r - 1];
//    printf("%d", min(res1, res2));
//    return 0;
//}

//bool check(char a)
//{
//    if (a == '(' || a == ')' || a == '[' || a == ']' || a == '{' || a == '}') return true;
//    return false;
//}
//bool is_match(char a, char b)
//{
//    if (a == '(' && b == ')') return true;
//    if (a == '[' && b == ')') return true;
//    if (a == '{' && b == '}') return true;
//    return false;
//}
//bool chkParenthesis(string A, int n) {
//    stack <char> s;
//    for (int i = 0; i < n; i++)
//    {
//        char t = A[i];
//        if (!check(t)) return false;
//        if (t != ')' && t != ']' && t != '}')
//        {
//            s.push(t);
//        }
//        else
//        {
//            if (s.empty()) return false;
//            int c = s.top();
//            if (!is_match(c, t)) return false;
//            s.pop();
//        }
//    }
//    if (s.empty()) return true;
//    return false;
//}
//
//int main()
//{
//    string s;
//    cin >> s;
//    cout << chkParenthesis(s,s.size());
//}

//const int N = 100010;
//int n, m;
//int a[N];
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++) cin >> a[i];
//    if (n == 2) cout << a[0] * a[1];
//    else
//    {
//        int tot = 0;
//        m = a[0] + a[1];
//        tot = a[0] * a[1];
//        for (int i = 2; i < n; i++)
//        {
//            tot += m * a[i];
//            m += a[i];
//        }
//        cout << tot;
//    }
//    return 0;
//}

//const int N = 10010;
//int n, T;
//int s[N];
//vector<vector<int>> vv;
//
//bool check(int a, int b)
//{
//    for (int i = 0; i < vv[a].size(); i++)
//    {
//        if (vv[a][i] == b) return true;
//    }
//    return false;
//}
//
//int main()
//{
//    scanf("%d%d", &n, &T);
//    vv.resize(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        vector<int>v;
//        v.reserve(n);
//        vv[i] = v;
//    }
//    while (T--)
//    {
//        int t, a, b;
//        scanf("%d%d%d", &t, &a, &b);
//        if (t == 1)
//        {
//            if (check(a, b)) continue;
//            vv[a].push_back(b);
//            vv[b].push_back(a);
//        }
//        else
//        {
//            s[a] += b;
//            for (int i = 0; i < vv[a].size(); i++)
//            {
//                s[vv[a][i]] += b;
//            }
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        printf("%d ", s[i]);
//    }
//    return 0;
//}

//int main()
//{
//    long long n;
//    scanf("%lld", &n);
//    n /= 1000;
//    int h = 0, m = 0, s = 0;
//    h = n / 60 / 60 % 24;
//    m = n / 60 % 60;
//    s = n % 60;
//    printf("%0.2d:%0.2d:%0.2lld", h, m, s);
//    return 0;
//}